#include <iostream>
#include <functional>
#include <iterator>
#include "../LazyLib/stdext.h"

using namespace std;

int partition1(int* a, int i1, int i2)
{
	int x = a[i2];
	int i = i1 - 1;
	for(int j = i1; j < i2; j++)
	{
		if(a[j] <= x)
		{
			i++;
			int tmp = a[j];
			a[j] = a[i];
			a[i] = tmp;
		}
	}

	int tmp = a[i2];
	a[i2] = a[i+1];
	a[i+1] = tmp;

	return i+1;

}


void qsort(int* a, int i1, int i2)
{
	if(i1 >= i2) return;
	int place = partition1(a, i1, i2);
	qsort(a, i1, place - 1);
	qsort(a, place + 1, i2);
}



int main()
{
	int a[10] = {1, 7, 9, 0, 5, 5, 3, 2, 11, 9};
	int size = sizeof(a)/sizeof(a[0]);
	cout << size << endl;
	qsort(a, 0, size - 1);
	copy(begin(a), end(a), ostream_iterator<int>(cout, ","));
	cout << endl;
}


